# 二叉树的最大深度： https://leetcode-cn.com/problems/maximum-depth-of-binary-tree/submissions/

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

# 这道题 使用，深度广度优先遍历都能解

class Solution:
    def maxDepth(self, root: TreeNode) -> int:
        """
            深度优先遍历：使用前序遍历
        """
        deepth = 0
        def dfs(node, deep):
            """ 使用前序: 递归实现 """
            nonlocal deepth
            if not node:
                return 

            if node.left: dfs(node.left, deep + 1)
            if node.right: dfs(node.right, deep + 1)

            deepth = max(deepth, deep)

        dfs(root, 1)    

        return deepth


class Solution:
    def maxDepth(self, root: TreeNode) -> int:
        """
            深度优先遍历, 使用前序: 显示栈
        """
        if not root: return 0
        
        deepth = 1
        stack = list()
        stack.append((root, 1))
        deepth = 0
        while stack:
            n = stack.pop()
            node, deep = n[0], n[1]
            deepth = max(deepth, deep)
            if node.right: stack.append((node.right, deep + 1))
            if node.left: stack.append((node.left, deep + 1))

        return deepth


# 这道题还可以使用后序遍历， 自底向上的求 ：当前树的深度 = max(左，右子树深度) + 1
# 可以使用后序遍历，递归求解

""" 和记录的拿到牛客的题是一样的， 那道题也是使用后序遍历，只是最后求得是左右子树是否相等，这里是左右字数的最大深度 """
